{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Lecture 2 : Linear Algebra\n",
    "**References:**\n",
    "* [Introduction to Symbolic Computation](http://homepages.math.uic.edu/~jan/mcs320/mcs320notes/index.html), Lecture [29](http://homepages.math.uic.edu/~jan/mcs320/mcs320notes/lec29.html)\n",
    "* [Linear Algebra tutorial in SageMath](https://doc.sagemath.org/html/en/tutorial/tour_linalg.html)\n",
    "* [Sage Quickstart for Linear Algebra](https://doc.sagemath.org/html/en/prep/Quickstarts/Linear-Algebra.html)\n",
    "\n",
    "**Summary:**<br>\n",
    "We start with a reminder on **lists** in Python, and functions for creating and manipulating them. Then we discuss **matrices** in SageMath: how to construct them, how to solve linear systems of equations, computer kernels and eigenvalues etc. Finally, we discuss **linear spaces** and how to intersect or add them."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Python warmup : lists\n",
    "Recall that in Python, a **list** ``L`` is an ordered collection of objects. They can be created by hand, using square brackets ``[,]``:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "L = [3, sin, pi, -12/5]; L"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "You can access element number ``i`` in the list (with count starting from ``0``) using ``L[i]``:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "L[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "L[1]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This can also be used to change an element of the list:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "L[1] = cos\n",
    "L"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Lists have many useful functions: \n",
    "* you can get the number of elements in ``L`` using ``len(L)``\n",
    "* given a second list ``M`` you can compute the concatenation of ``L`` and ``M`` by ``L+M``\n",
    "* you can check if ``a`` is contained in ``L`` by the expression ``a in L``\n",
    "\n",
    "#### Exercise\n",
    "* Create a list ``M`` with 3 elements of your choice."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* Define ``N`` to be the list obtained by concatenating ``L`` (from above) and ``M``."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* Check that the length of ``N`` is now equal to 7."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Solution** (uncomment to see)\n",
    "<!---\n",
    "```\n",
    "M = [6, 3, [1,2,3]]\n",
    "N = L+M; N\n",
    "> [3, cos, pi, -12/5, 6, 3, [1, 2, 3]]\n",
    "len(N)\n",
    "> 7\n",
    "```\n",
    "--->"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A list ``L`` also has many useful methods, like ``L.pop(i)`` which returns ``L[i]`` **and** removes this entry from the list. As we saw last week, you can see all these methods by typing ``L.``+``Tab`` to access the Tab completion."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Exercise\n",
    "Consider the following list:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "L = [77, 23, 49, 66, 39, 26, 48, 23, 35, 70, 64, 9, 21, 15, 78, 21, 2, 56, 42, 53]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* What is the number ``i`` such that ``L[i]`` equals ``9``?<br>*Hint:* Use Tab completion and the documentation to find the right function."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* Remove the corresponding entry from the list."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Solution** (uncomment to see)\n",
    "<!---\n",
    "```\n",
    "L.index(9)\n",
    "> 11\n",
    "L.pop(11)\n",
    "> 9\n",
    "L\n",
    "> [77, 23, 49, 66, 39, 26, 48, 23, 35, 70, 64, 21, 15, 78, 21, 2, 56, 42, 53]\n",
    "```\n",
    "--->"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Finally, a nice way to create bigger lists is using **list comprehension** involving the ``for`` constructor. We will learn more about this and ``for``-loops later, but for now we just mention that\n",
    "```\n",
    "[f(i) for i in range(n)]\n",
    "```\n",
    "creates the list ``[f(0), f(1), ..., f(n-1)]``, and similarly\n",
    "```\n",
    "[f(i) for i in range(a,b)]\n",
    "```\n",
    "creates the list ``[f(a), f(1), ..., f(b-1)]``."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "[3*i+2 for i in range(7)]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Exercise\n",
    "You get an email from a local school, asking for help since they misplaced some of their math education materials. In particular, they request whether you can send them:\n",
    "* a list of the square numbers 1^2, ..., 20^2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* a multiplication table for the numbers from 1 to 10"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Solution** (uncomment to see)\n",
    "<!---\n",
    "```\n",
    "[a^2 for a in range(1,21)]\n",
    "> \n",
    "[1,\n",
    " 4,\n",
    " 9,\n",
    " 16,\n",
    " 25,\n",
    " 36,\n",
    " 49,\n",
    " 64,\n",
    " 81,\n",
    " 100,\n",
    " 121,\n",
    " 144,\n",
    " 169,\n",
    " 196,\n",
    " 225,\n",
    " 256,\n",
    " 289,\n",
    " 324,\n",
    " 361,\n",
    " 400]\n",
    "```\n",
    "For the multiplication table, we use a command ``matrix`` below since the output looks nicer, but you can also leave away the ``matrix`` function and produce a list of lists.\n",
    "```\n",
    "matrix([[a*b for a in range(1,11)] for b in range(1,11)])\n",
    "> \n",
    "[  1   2   3   4   5   6   7   8   9  10]\n",
    "[  2   4   6   8  10  12  14  16  18  20]\n",
    "[  3   6   9  12  15  18  21  24  27  30]\n",
    "[  4   8  12  16  20  24  28  32  36  40]\n",
    "[  5  10  15  20  25  30  35  40  45  50]\n",
    "[  6  12  18  24  30  36  42  48  54  60]\n",
    "[  7  14  21  28  35  42  49  56  63  70]\n",
    "[  8  16  24  32  40  48  56  64  72  80]\n",
    "[  9  18  27  36  45  54  63  72  81  90]\n",
    "[ 10  20  30  40  50  60  70  80  90 100]\n",
    "```\n",
    "--->"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Matrices\n",
    "At the center of linear algebra are *matrices*, which describe linear maps between finite-dimensional vector spaces. \n",
    "\n",
    "### Constructing matrices\n",
    "From last time, we recall that we can create matrices using the function ``matrix``. We saw that it can handle at least two different types of input:\n",
    "* ``matrix([v1, v2, ..., vm])`` takes a **list**  of vectors, forming the rows of the desired matrix,\n",
    "* ``matrix(m,n,f)`` takes the numbers ``m,n`` of rows and columns of the matrix $M$, and a function ``f`` sending pairs $(i,j)$ to the desired entry $M_{i,j}$ of the matrix"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Exercise\n",
    "The **Vandermonde matrix** associated to a vector $a=(a_1, \\ldots, a_n)$ of numbers is the matrix\n",
    "$$\n",
    "V(a_1, \\ldots, a_n)=\n",
    "\\begin{pmatrix}\n",
    "1 & a_1 & \\ldots & a_1^{n-1}\\\\\n",
    "1 & a_2 & \\ldots & a_2^{n-1}\\\\\n",
    "\\vdots & & & \\vdots\\\\\n",
    "1 & a_n & \\ldots & a_n^{n-1}\n",
    "\\end{pmatrix}\\,.\n",
    "$$\n",
    "Below is the beginning of an implementation of the function taking a list ``a`` of numbers and returning the corresponding Vandermonde matrix. Complete the program and test it in some examples."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def vandermonde_matrix(a):\n",
    "    n = len(a)\n",
    "    return ???"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Solution** (uncomment to see)<br>\n",
    "<!---\n",
    "There are two possible ways to implement the Vandermonde matrix:\n",
    "* via lists\n",
    "\n",
    "```\n",
    "def vandermonde_matrix(a):\n",
    "    n = len(a)\n",
    "    return matrix([[a[i]^j for j in range(n)] for i in range(n)])\n",
    "```\n",
    "* via a function (we use the ``lambda`` constructor for a quick function definition below)\n",
    "\n",
    "```\n",
    "def vandermonde_matrix2(a):\n",
    "    n = len(a)\n",
    "    return matrix(n,n, lambda i,j : a[i]**j)\n",
    "```\n",
    "Then we can test our function:\n",
    "```\n",
    "vandermonde_matrix([2,3,4,5])\n",
    "> \n",
    "[  1   2   4   8]\n",
    "[  1   3   9  27]\n",
    "[  1   4  16  64]\n",
    "[  1   5  25 125]\n",
    "```\n",
    "--->"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "One further possibility to construct a matrix by hand is to call ``matrix`` with a **dictionary**. We are going to discuss these later in more detail, but below is a hopefully self-explaining example:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "matrix(2,3,{(0,1):17, (1,2):-3})"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For many standard types of matrices, there are also pre-defined functions:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "matrix.zero(2,3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "matrix.diagonal([5,-1,0,-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "A = matrix([[3,9],[6,10]])\n",
    "block_matrix([ [A, -A], [A.transpose(), 100*A] ], subdivide=False)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "On the other hand, if someone hands you a matrix ``M``, you can find out its number of rows and columns using ``M.nrows()`` and ``M.ncols()``:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "M = matrix([[10,9,8],[7,6,5]])\n",
    "M"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "M.nrows()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "M.ncols()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "You can access the entry $M_{i,j}$ using ``M[i,j]``:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "M[0,1]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Sometimes it can be useful to explicitly specify that a matrix should have entries in a certain ring. This ring can then be given as the first argument to the ``matrix`` function.\n",
    "\n",
    "Some common rings:\n",
    "* ``ZZ`` the integers\n",
    "* ``QQ`` the rational numbers\n",
    "* ``RR`` the real numbers (floating point operations!)\n",
    "* ``CC`` the complex numbers (floating point operations!)\n",
    "* ``GF(q)`` the finite field $\\mathbb{F}_q$ with $q$ elements\n",
    "\n",
    "#### Example\n",
    "The matrix\n",
    "$$\n",
    "M = \\begin{pmatrix} 1 & 1 \\\\ 3 & 5 \\end{pmatrix}\n",
    "$$\n",
    "has rank $2$ seen as a matrix of rational numbers. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "M = matrix(ZZ,[[1,1],[3,5]])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "M.rank()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "But over the finite field $\\mathbb{F}_2 = \\mathbb{Z}/2\\mathbb{Z}$ we have\n",
    "$$\n",
    "M = \\begin{pmatrix} 1 & 1 \\\\ 3 & 5 \\end{pmatrix} = \\begin{pmatrix} 1 & 1 \\\\ 1 & 1 \\end{pmatrix}\n",
    "$$\n",
    "and so the matrix only has rank $1$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "M = matrix(GF(2),[[1,1],[3,5]])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "M.rank()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Exercise\n",
    "Find a formula for the determinant $\\det(V(a_1, \\ldots, a_n))$ of the Vandermonde matrix. Bonus points if you can get the sign correct ...<br>\n",
    "*Hint:* Another useful ring is a polynomial ring, which you can construct as follows:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "R.<a,b,c> = PolynomialRing(QQ,3) # here 3 is the number of variables\n",
    "R"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "f = a^2 + 2*a*b + b^2\n",
    "factor(f)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Solution** (uncomment to see)<br>\n",
    "<!---\n",
    "We take the hint and construct a *general* Vandermonde matrix, compute its determinant and factor it:\n",
    "```\n",
    "R.<a,b,c,d> = PolynomialRing(QQ,4)\n",
    "M = matrix.vandermonde([a,b,c])\n",
    "f = M.determinant()\n",
    "factor(f)\n",
    "> (b - c) * (-a + b) * (a - c)\n",
    "M = matrix.vandermonde([a,b,c,d])\n",
    "f = M.determinant()\n",
    "factor(f)\n",
    "> (-1) * (c - d) * (-b + c) * (b - d) * (-a + c) * (-a + b) * (a - d)\n",
    "```\n",
    "From this we see that the formula must be something like\n",
    "$$\n",
    "\\det(V(a_1, \\ldots, a_n)) = \\prod_{1 \\leq i < j \\leq n} a_j - a_i\n",
    "$$\n",
    "and checking the sign in a few cases, this is indeed the [right formula](https://en.wikipedia.org/wiki/Vandermonde_matrix).\n",
    "--->"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Linear algebra with matrices\n",
    "Now that we can input matrices, we can start doing more interesting computations. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Matrix arithmetic and vector products\n",
    "We already saw that we can perform matrix arithmetic with ``+,*,^``:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "M = matrix([[2,6],[0,-7]])\n",
    "N = matrix([[1,0],[2,-9]])\n",
    "[M+N, M*N, M^2]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In particular, when ``M`` is invertible, we can compute its inverse by ``M^(-1)`` (or ``M.inverse()``):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "M^(-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "M.inverse()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Note that you can also compute the expression $M^x$ for a formal variable $x$. Below we use that in SageMath ``x`` is by default a variable in the **symbolic ring**, which we will see later."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "M^x"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can also create **vectors** and multiply them with matrices."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "v = vector([2,-5])\n",
    "M*v"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Row echelon form\n",
    "Another interesting computation for a matrix $M$ is its **row echelon form** (German: Zeilenstufenform), which is the simplified form of $M$ obtained by row-operations."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "M = matrix(QQ,[[2,4,-1,7],[-3,-6,3,-2],[1,2,5,-8]])\n",
    "M"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "M.echelon_form()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Note that if we work over the integers ``ZZ``, the algorithm only does integer operations on the rows (it is not allowed to divide a row by a number), so the output will be slightly different:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "M = matrix(ZZ,[[2,4,-1,7],[-3,-6,3,-2],[1,2,5,-8]])\n",
    "M.echelon_form()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can also get the matrix $U$ describing the row-operations to bring $M$ into echelon form $E$, so that $U \\cdot M = E$:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "E, U = M.echelon_form(transformation=True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "U"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "U*M"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Exercise\n",
    "Does there exist a subset of the vectors\n",
    "$$\n",
    "v_1 = \\begin{pmatrix}-2\\\\ 5\\\\ 3 \\end{pmatrix},\n",
    "v_2 = \\begin{pmatrix}4\\\\ -10\\\\ -6 \\end{pmatrix},\n",
    "v_3 = \\begin{pmatrix}1 \\\\0 \\\\ -7 \\end{pmatrix},\n",
    "v_4 = \\begin{pmatrix} -1\\\\ 5\\\\ -4 \\end{pmatrix},\n",
    "v_5 = \\begin{pmatrix} -5\\\\ 10\\\\ 13 \\end{pmatrix},\n",
    "v_6 = \\begin{pmatrix} 5\\\\ -2\\\\ -11 \\end{pmatrix},\n",
    "v_7 = \\begin{pmatrix} 9\\\\ -15\\\\ -30 \\end{pmatrix} \\in \\mathbb{R}^3\n",
    "$$\n",
    "which forms a basis of $\\mathbb{R}^3$? If so, specify such a subset.<br>\n",
    "*Hint:* To save you time, here is the list of the vectors above:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "V = [(-2, 5, 3),\n",
    " (4, -10, -6),\n",
    " (1, 0, -7),\n",
    " (-1, 5, -4),\n",
    " (-5, 10, 13),\n",
    " (5, -2, -11),\n",
    " (9, -15, -30)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Solution** (uncomment to see)\n",
    "<!---\n",
    "<br>\n",
    "If we form the $3 \\times 7$-matrix $M = (v_1 v_2 \\ldots v_7)$ we can check that the rank of $M$ is $3$:\n",
    "``` \n",
    "M = matrix(QQ,V).transpose()\n",
    "M.rank()\n",
    "> 3\n",
    "```\n",
    "So the vectors $v_i$ indeed form a generating set of $\\mathbb{R}^3$. To choose a basis, we can then compute the row echelon form. \n",
    "```\n",
    "matrix(QQ,V).transpose().echelon_form()\n",
    ">\n",
    "[ 1 -2  0  1  2  0 -3]\n",
    "[ 0  0  1  1 -1  0  3]\n",
    "[ 0  0  0  0  0  1  0]\n",
    "```\n",
    "**Claim**: the columns where this form has a new step are precisely the indices of a possible basis (in the case above, this gives $v_1, v_3, v_6$). Indeed, to get such a basis, we want to have the indices such that\n",
    "$$ \n",
    "\\mathrm{rank} (v_1 v_2 \\ldots v_{i-1}) < \\mathrm{rank} (v_1 v_2 \\ldots v_{i})\n",
    "$$\n",
    "But row operations do not change the ranks of these submatrices and in the row echelon form, it's clear that the rank goes up precisely when we have a new step of the row echelon form.\n",
    "\n",
    "You can also get these indices directly (starting the count from $0$ as usual) using the command\n",
    "```\n",
    "M.pivots()\n",
    "> (0, 2, 5)\n",
    "```\n",
    "--->"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Solving linear equations\n",
    "Of course, we can also solve linear systems of equations using SageMath: given a matrix ``M`` and a vector ``b`` the solution of the linear system\n",
    "$$\n",
    "M \\cdot x = b\n",
    "$$\n",
    "is computed using ``M.solve_right(b)``."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "M = matrix([[1,2],[3,4]])\n",
    "b = vector([1,2])\n",
    "[M, b]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "v=M.solve_right(b)\n",
    "v"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "M*v"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "As the name suggests, there is also the methods ``M.solve_left(b)``, which solves the equation\n",
    "$$\n",
    "x^T \\cdot M = b^T,\n",
    "$$\n",
    "where $x^T, b^T$ are the transposed (or row) vectors of $x,b$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "w = M.solve_left(b)\n",
    "w"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Exercise\n",
    "Find out what ``M.solve_right(b)`` does when the system has\n",
    "* more than one solution, or\n",
    "* no solution,\n",
    "\n",
    "either by reading the documentation or by experimenting."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Solution** (uncomment to see)<br>\n",
    "<!---\n",
    "An example of a linear system with more than one solution is\n",
    "$$\n",
    "\\begin{pmatrix}\n",
    "1 & 1\n",
    "\\end{pmatrix} \\cdot\n",
    "\\begin{pmatrix}\n",
    "x_1\\\\ x_2\n",
    "\\end{pmatrix} = \\begin{pmatrix} 1 \\end{pmatrix}.\n",
    "$$\n",
    "Applying ``solve_right``, we obtain:\n",
    "```\n",
    "M = matrix([[1,1]])\n",
    "b = vector([1])\n",
    "M.solve_right(b)\n",
    "> (1, 0)\n",
    "```\n",
    "So SageMath just gives us **one** solution, and to obtain the full set of solutions we should add the (right) kernel of ``M``, which we discuss below.\n",
    "\n",
    "An example of a system with no solution is\n",
    "$$\n",
    "\\begin{pmatrix}\n",
    "1 \\\\ 1\n",
    "\\end{pmatrix} \\cdot\n",
    "\\begin{pmatrix}\n",
    "x\n",
    "\\end{pmatrix} = \\begin{pmatrix} 1 \\\\ 2 \\end{pmatrix}.\n",
    "$$\n",
    "Here, we get an error message, stating that the system has no solutions:\n",
    "```\n",
    "M = matrix([[1],[1]])\n",
    "b = vector([1,1])\n",
    "M.solve_right(b)\n",
    "> ---------------------------------------------------------------------------\n",
    "  ValueError ...\n",
    "  ...\n",
    "  ValueError: matrix equation has no solutions\n",
    "```\n",
    "--->"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Further matrix functions\n",
    "As you can imagine, there are many more things that SageMath can compute about matrices. Instead of going through all of them, let's have an exercise where you can practice finding out about some of these functions yourself. In this regard, the following advice has proven useful in the past:\n",
    "\n",
    "<center>\n",
    "    <b>SageMath-Tip No. 4<br>Just google it.</b>    \n",
    "</center>\n",
    "\n",
    "**Exercise**\n",
    "Consider the following matrix:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "M = matrix(QQ,[(29, -3, -3, -27, -24),(30, -1, 6, -12, -54),(-30, 6, -4, 6, 60),(18, -3, 0, -10, -24),(3, 0, -3, -9, 8)])\n",
    "M"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* What are the **eigenvalues** of ``M``?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* Compute a matrix $S$ such that $S M S^{-1}$ is a diagonal matrix."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* Compute a permutation matrix $P$, a lower-triangular matrix $L$ and an upper triangular matrix $U$ such that $A = PLU$. <br>(*Hint:* This is often called a **LU-decomposition**)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* Is $M$ a **normal** matrix, i.e. does it satisfy $M \\cdot M^\\top = M^\\top \\cdot M$?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Solution** (uncomment to see)\n",
    "<!---\n",
    "```\n",
    "M.eigenvalues()\n",
    "> [8, 5, 5, 2, 2]\n",
    "D, S = M.diagonalization()\n",
    "S.inverse()*M*S\n",
    "> \n",
    "[8 0 0 0 0]\n",
    "[0 5 0 0 0]\n",
    "[0 0 5 0 0]\n",
    "[0 0 0 2 0]\n",
    "[0 0 0 0 2]\n",
    "S.inverse() # this is the matrix we want!\n",
    "> \n",
    "[  5   0   0  -5  -5]\n",
    "[ -1  -1  -1   1   2]\n",
    "[  2  -1   2   4 -10]\n",
    "[ -3   1   1   4   3]\n",
    "[ -6   2  -2   0  14]\n",
    "P, L, U = M.LU()\n",
    "P\n",
    ">\n",
    "[0 0 1 0 0]\n",
    "[1 0 0 0 0]\n",
    "[0 1 0 0 0]\n",
    "[0 0 0 0 1]\n",
    "[0 0 0 1 0]\n",
    "L\n",
    ">\n",
    "[      1       0       0       0       0]\n",
    "[     -1       1       0       0       0]\n",
    "[  29/30 -61/150       1       0       0]\n",
    "[   1/10    1/50 273/599       1       0]\n",
    "[    3/5  -12/25 198/599   13/27       1]\n",
    "U\n",
    ">\n",
    "[      30       -1        6      -12      -54]\n",
    "[       0        5        2       -6        6]\n",
    "[       0        0  -599/75  -446/25   766/25]\n",
    "[       0        0        0  270/599 -410/599]\n",
    "[       0        0        0        0    40/27]\n",
    "M.is_normal()\n",
    "> False\n",
    "```\n",
    "--->"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Linear spaces\n",
    "In SageMath we can also directly create vector spaces and perform computations with subspaces (like direct sums, intersections etc.)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "V = VectorSpace(QQ,3)\n",
    "V"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Then we can create subspaces of ``V``:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "W1 = V.subspace([(1,2,3), (1,1,1)])\n",
    "W2 = V.subspace([(1,-1,1), (0,0,1)])\n",
    "W1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Here ``degree 3`` means that the ambient space ``V`` has is of rank 3, and ``dimension 2`` means that ``W1`` itself is of dimension 2.\n",
    "\n",
    "Now we can check if a vector is contained in one of those subspaces, or compute their intersection or sum in ``V``."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "vector(QQ,[1,2,3]) in V"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "W1.intersection(W2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "W1+W2"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "An alternative way to create subspaces is using the function ``span``:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "W1alt = span(QQ,[(1,2,3), (1,1,1)])\n",
    "W1 == W1alt"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Exercise\n",
    "Consider the following vectors in $\\mathbb{Q}^4$:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "v = vector(QQ,[4,-3,2,6])\n",
    "w1 = vector(QQ,[1,-7,-3,0])\n",
    "w2 = vector(QQ,[9,-4,-4,1])\n",
    "w3 = vector(QQ,[-15,21,8,-7])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Use the methods for linear spaces we saw above, to answer the following questions:\n",
    "* Are $w_1, w_2, w_3$ linearly independent?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* Is $v$ contained in the subspace of $\\mathbb{Q}^4$ generated by $w_1, w_2, w_3$?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Solution** (uncomment to see)<br>\n",
    "<!---\n",
    "We create the span of $w_1, w_2, w_3$ and check its dimension:\n",
    "```\n",
    "W = span(QQ,[w1,w2,w3])\n",
    "W\n",
    "> Vector space of degree 4 and dimension 3 over Rational Field\n",
    "Basis matrix:\n",
    "[       1        0        0  119/251]\n",
    "[       0        1        0 -124/251]\n",
    "[       0        0        1  329/251]\n",
    "```\n",
    "Since the dimension is $3$, the vectors are indeed linearly independent. Then we can check if $v$ is contained in the space $W$:\n",
    "```\n",
    "v in W\n",
    "> True\n",
    "```\n",
    "--->"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Of course one could also find the answer to these questions using matrices, and in the background this is what SageMath does. Given a space like ``W1``, you can get access to the matrix whose rows form a basis of ``W1`` using ``W1.basis_matrix()``:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "W1.basis_matrix()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Exercise\n",
    "Let's apply the concepts from above to write a nice function ourselves, which computes orthogonal projections. Recall that given a sub-vector space $V \\subseteq \\mathbb{R}^n$ and a point $p \\in \\mathbb{R}^n$, the **orthogonal projection** of $p$ onto $V$ is the unique point $p_0 \\in V$ such that the vector $p-p_0$ is orthogonal to $V$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "f = (lambda u,v: u+v, lambda u,v: u, lambda u,v: v)\n",
    "plane = parametric_plot3d(f, (-2,2), (-2,2))\n",
    "arrow = arrow3d((5/3, 4/3, 1/3), (1,2,1), 1, color='red')\n",
    "plane + arrow"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* Complete the definition of the function ``orthogonal_projection`` below, which takes as input the vector space ``V`` and the vector ``p`` and returns the orthogonal projection ``p_0`` as above."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def orthogonal_projection(V, p):\n",
    "    return ???"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Hint*: If $v_1, \\ldots, v_m \\in V$ is a basis of $V$, then there exist numbers $x_1, \\ldots, x_m$ such that $p_0 = x_1 v_1 + \\ldots + x_m v_m$. Reformulate the condition that $p - p_0$ is orthogonal to $V$ as a linear system $A \\cdot x = b$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* Test your function in some non-trivial example."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Solution** (uncomment to see) <br>\n",
    "<!---\n",
    "If $M$ is the matrix whose rows are basis elements of $V$, then for the row vector $x = (x_1, \\ldots, x_m)$ a general element $p_0$ of $V$ is given by $x \\cdot M$. This element is the orthogonal projection of $p$ if $p_0-p$ is orthogonal to $V$, i.e. if its scalar product with all basis vectors of $V$ is zero. This condition can be written as:\n",
    "$$\n",
    "\\left(\\underbrace{x \\cdot M}_{=p_0} - p \\right) \\cdot M^\\top = 0 \\quad \\iff \\quad x \\cdot (M \\cdot M^\\top) = p \\cdot M^\\top = (M \\cdot p)^\\top\n",
    "$$\n",
    "This is a (left) equation with matrix $M \\cdot M^\\top$ and right-hand side $M \\cdot p$, seen as a row vector. Thus the following code computes the answer:\n",
    "```\n",
    "def orthogonal_projection(V, p):\n",
    "    M = V.basis_matrix()\n",
    "    x = (M*M.transpose()).solve_left(M*p)\n",
    "    v = x*M\n",
    "    assert v in V and (v-p) in V.complement()\n",
    "    return v\n",
    "```\n",
    "Note that we use an ``assert`` statement before returning the answer to check that our answer ``v`` lies in the space $V$ and satisfies that the difference ``v-p`` is in the orthogonal complement of $V$. We don't need this line for the output, but it's a good check that our code works.\n",
    "\n",
    "To do a check in a concrete example, we project the point $(1,0)$ to the line spanned by $(1,-1)$ in $\\mathbb{R}^2$:\n",
    "```\n",
    "V = span(QQ,[[1,-1]])\n",
    "p = vector([1,0])\n",
    "orthogonal_projection(V, p)\n",
    "> (1/2, -1/2)\n",
    "```\n",
    "--->"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Assignments"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Exercise\n",
    "For which values of $x \\in \\mathbb{Q}$ is the matrix\n",
    "$$\n",
    "M(x) = \n",
    "\\begin{pmatrix}\n",
    "-2 & 3 & x \\\\ -5 & x & 6 \\\\ 1 & -1 & 0\n",
    "\\end{pmatrix}\n",
    "$$\n",
    "invertible?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Solution** (uncomment to see)<br>\n",
    "<!---\n",
    "The matrix is invertible iff its determinant is nonzero. Thus we can compute this determinant (in dependence of $x$) and find its zeros by factoring it:\n",
    "```\n",
    "R.<x> = PolynomialRing(QQ,1)\n",
    "M = matrix([[-2,3,x],[-5,x,6],[1,-1,0]])\n",
    "factor(M.determinant())\n",
    "> (-1) * (x - 6) * (x + 1)\n",
    "```\n",
    "Thus the matrix is invertible precisely for $x \\in \\mathbb{Q} \\setminus \\{-1,6\\}$.\n",
    "--->"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Exercise\n",
    "Write a function ``jordan_form(blocks)`` taking as input a list ``blocks`` of the form ``[[e1,m1], ..., [en,mn]]`` of pairs ``[ei,mi]`` of eigenvalues and multiplicities, and producing the corresponding Jordan block diagonal matrix. Here is an example how it would work:\n",
    "```\n",
    "jordan_form([[3,2],[4,1],[-1,3]])\n",
    ">\n",
    "[ 3  1  0  0  0  0]\n",
    "[ 0  3  0  0  0  0]\n",
    "[ 0  0  4  0  0  0]\n",
    "[ 0  0  0 -1  1  0]\n",
    "[ 0  0  0  0 -1  1]\n",
    "[ 0  0  0  0  0 -1]\n",
    "```\n",
    "For an easier variant of the exercise: try to create the particular $6 \\times 6$-matrix above with as little code as possible."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Solution** (uncomment to see)<br>\n",
    "<!---\n",
    "There is a quick way to do the exercise, using pre-defined functions: we first create a list of the individual jordan blocks using ``matrix.jordan_block`` and then form the block diagonal matrix consisting of them:\n",
    "```\n",
    "def jordan_form(blocks):\n",
    "    n = len(blocks)\n",
    "    jordan_matrices = [matrix.jordan_block(blocks[i][0],blocks[i][1]) for i in range(n)]\n",
    "    return matrix.block_diagonal(jordan_matrices,subdivide=False)\n",
    "```\n",
    "Later, when we have ``for``-loops, and ``if``-conditions, we could also construct this matrix by hand, with a bit of more work. \n",
    "--->"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Exercise\n",
    "Consider the following matrix:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 74,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[    1812     2239       -3        1    17711]\n",
       "[ -158013  -195140     2067     -689 -1543587]\n",
       "[    -189     -234      153      -50    -1851]\n",
       "[    -567     -702      465     -152    -5553]\n",
       "[   19791    24441     -261       87   193332]"
      ]
     },
     "execution_count": 74,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "rows = [(1812, 2239, -3, 1, 17711),\n",
    " (-158013, -195140, 2067, -689, -1543587),\n",
    " (-189, -234, 153, -50, -1851),\n",
    " (-567, -702, 465, -152, -5553),\n",
    " (19791, 24441, -261, 87, 193332)]\n",
    "M = matrix(rows); M"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Compute its characteristic polynomial and minimal polynomial. Why are they different?<br>\n",
    "*Bonus:* See the solution for an explanation how the hell I came up with this matrix."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Solution** (uncomment to see)\n",
    "<!---\n",
    "```\n",
    "c = M.characteristic_polynomial(); c\n",
    "> x^5 - 5*x^4 - 5*x^3 + 45*x^2 - 108\n",
    "factor(c)\n",
    "> (x + 2)^2 * (x - 3)^3\n",
    "m = M.minimal_polynomial(); m\n",
    "> x^4 - 2*x^3 - 11*x^2 + 12*x + 36\n",
    "factor(m)\n",
    "> (x - 3)^2 * (x + 2)^2\n",
    "```\n",
    "Looking at the Jordan normal form, we see that the reason for the discrepancy is that it has two Jordan blocks for the eigenvalue $3$ (and the power $(x-3)^2$ in the minimal polynomial tells us that the larger of the two has size two):\n",
    "```\n",
    "M.jordan_form()\n",
    ">\n",
    "[-2  1| 0  0| 0]\n",
    "[ 0 -2| 0  0| 0]\n",
    "[-----+-----+--]\n",
    "[ 0  0| 3  1| 0]\n",
    "[ 0  0| 0  3| 0]\n",
    "[-----+-----+--]\n",
    "[ 0  0| 0  0| 3]\n",
    "```\n",
    "*Bonus:*\n",
    "I created the matrix by first forming the Jordan form I wanted (using the exercise above), and conjugating it with a random element of $\\mathrm{SL}_6(\\mathbb{Z})$, to ensure that the result of the conjugation was an integer valued matrix. However, since no easy way to create such a random elements was available, I had to improvise: I took generators $A,B,C,D$ of $\\mathrm{SL}_6(\\mathbb{Z})$ and then formed a product of elements $A^a B^b C^c D^d$ for random integers $a,b,c,d$.\n",
    "```\n",
    "J = jordan_form([[3,1],[3,2],[-2,2]]); J\n",
    ">\n",
    "[ 3  0  0  0  0]\n",
    "[ 0  3  1  0  0]\n",
    "[ 0  0  3  0  0]\n",
    "[ 0  0  0 -2  1]\n",
    "[ 0  0  0  0 -2]\n",
    "G=SL(5,ZZ)\n",
    "A,B,C,D = G.gens()\n",
    "L = [[randint(-10,10) for i in range(4)] for j in range(15)]\n",
    "P = prod(A^a * B^b * C^c * D^d for (a,b,c,d) in L)\n",
    "P\n",
    ">\n",
    "[    9    28     0    -1     0]\n",
    "[ -648 -2016   -87   689     0]\n",
    "[   -1    -3     0     0   -10]\n",
    "[   -3    -9     0     0   -31]\n",
    "[   81   252    11   -87     0]\n",
    "S = matrix(P)\n",
    "M = S * J * S^(-1); M\n",
    ">\n",
    "[    1812     2239       -3        1    17711]\n",
    "[ -158013  -195140     2067     -689 -1543587]\n",
    "[    -189     -234      153      -50    -1851]\n",
    "[    -567     -702      465     -152    -5553]\n",
    "[   19791    24441     -261       87   193332]\n",
    "```\n",
    "--->"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Exercise\n",
    "Inside $\\mathbb{R}^3$ with coordinates $x_1, x_2, x_3$ consider the subspace\n",
    "$$\n",
    "V = \\{(x_1, x_2, x_3) : 2 x_1 - x_2 + 3 x_3 = 0\\}\\,.\n",
    "$$\n",
    "* Compute a basis $\\mathcal{B}$ of $V$.\n",
    "* For the linear map $f:\\mathbb{R}^3 \\to \\mathbb{R}^3$ induced by the matrix\n",
    "$$\n",
    "A = \\begin{pmatrix}\n",
    "3 & 5 & 0 \\\\ -2 & 6 & 8 \\\\ -1 & 1 & 7\n",
    "\\end{pmatrix}\n",
    "$$\n",
    "compute the matrix $A_V$ for the restriction $f|_V : V \\to \\mathbb{R}^3$ with respect to your chosen basis $\\mathcal{B}$ of $V$ and the standard basis of $\\mathbb{R}^3$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Solution** (uncomment to see)\n",
    "<!---\n",
    "```\n",
    "M = matrix([[2,-1,3]])\n",
    "V = M.right_kernel(); V\n",
    ">\n",
    "Free module of degree 3 and rank 2 over Integer Ring\n",
    "Echelon basis matrix:\n",
    "[1 2 0]\n",
    "[0 3 1]\n",
    "B = V.basis(); B\n",
    "> [\n",
    "(1, 2, 0),\n",
    "(0, 3, 1)\n",
    "]\n",
    "A = matrix([[3,5,0],[-2,6,8],[-1,1,7]])\n",
    "N = [A*vector(v) for v in B]; N\n",
    "> [(13, 10, 1), (15, 26, 10)]\n",
    "AV = matrix(N).transpose(); AV\n",
    ">\n",
    "[13 15]\n",
    "[10 26]\n",
    "[ 1 10]\n",
    "```\n",
    "--->"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "SageMath 9.1",
   "language": "sage",
   "name": "sagemath"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}